package Aleehot100;

import java.util.ArrayList;
import java.util.List;

/**
 * ClassName: c053
 * Package: Aleehot100
 * Description: 207 课程表
 *
 * @Author BCXJ
 * @Create 2025/8/5 08:32
 * @Version 1.0
 * @Since 1.0
 */
public class c053 {
    public static void main(String[] args) {
        int[][] arr = {{1, 0}};
        System.out.println(canFinish(2, arr));
    }

    public static boolean canFinish(int numCourses, int[][] prerequisites) {

        ArrayList<List<Integer>> edges = new ArrayList<>(numCourses); // 邻接表
        // 0 ~ n-1
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>()); // 初始化表，防止后续的NPE(NullPointException)
        }
        int[] inDegree = new int[numCourses]; // 入度表
        for (int i = 0; i < prerequisites.length; i++) {
            edges.get(prerequisites[i][1]).add(prerequisites[i][0]); // 邻接表加边
            inDegree[prerequisites[i][0]] ++; // 入度++
        }

        // 队列
        int[] queue = new int[numCourses]; int l = 0, r = 0;
        for (int i = 0; i < inDegree.length; i++) {
            if(inDegree[i] == 0) {
                queue[r++] = i;
            }
        }

        // 遍历队列
        int res = 0;
        while(l < r) {
            int cur = queue[l++];
            res ++;
            for (Integer node : edges.get(cur)) { // 遍历边然后入度 --
                if(-- inDegree[node] == 0) {
                    queue[r ++] = node;
                }
            }
        }

        return res == numCourses;
    }

}
